class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix[0][0]>target||matrix[matrix.length-1][matrix[0].length-1]<target)return false;
        int left = 0;
        int right = matrix.length-1;
        while(left < right){
            int mid = (left+right+1)>>1;
            if(matrix[mid][0]==target){
                return true;
            }else if(matrix[mid][0]>target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        int row = right;
        left = 0;
        right = matrix[0].length-1;
        while(left<right){
            int mid = (left + right +1) >>1;
            if(matrix[row][mid]==target){
                return true;
            }else if(matrix[row][mid]>target){
                right = mid-1;
            }else{
                left = mid;
            }
        }
        return right==-1?false:matrix[row][right]==target;
    }
}
/**
    二维二分
 */